package main

import "fmt"

/**
获取二叉树最低公共祖先问题
思路1，记录自己所有的父节点，然后遍历，获取第一个公共节点，就是对应的最小公共祖先
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//
//  lowestCommonAncestor
//  @Description: 返回两个二叉子树的最小公共祖先
//  @param root：
//  @param p：
//  @param q：
//  @return *TreeNode：
//
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || p == root || q == root {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	} else {
		return right
	}
}

func lca(root, p, q *TreeNode) *TreeNode {
	if root == nil || p == nil || q == nil {
		return root
	}
	fatherMap := make(map[*TreeNode]*TreeNode)
	fatherMap[root] = root // 头节点的父节点就是自己，一定要保存
	process(root, fatherMap)
	// 用一个集合保存p的所有父亲节点
	setP := make(map[*TreeNode]*TreeNode)
	for cur := p; cur != fatherMap[cur]; cur = fatherMap[cur] {
		if _, ok := setP[cur]; !ok {
			setP[cur] = fatherMap[cur]
		}
	}
	setP[root] = root
	for k, v := range setP {
		if k != nil {
			fmt.Println(k.Val, v.Val)
		}
	}
	for cur2 := q; cur2 != fatherMap[cur2]; cur2 = fatherMap[cur2] {
		if _, ok := setP[cur2]; ok {
			return cur2
		}
	}
	return nil
}

//
//  process
//  @Description: 从根节点开始，保存所有节点的父节点的关系，到哈希表中
//  @param root：
//  @param fatherHash：
//
func process(root *TreeNode, fatherHash map[*TreeNode]*TreeNode) {
	if root == nil {
		return
	}
	fatherHash[root.Left] = root
	fatherHash[root.Right] = root
	process(root.Left, fatherHash)
	process(root.Right, fatherHash)
}

func main() {
	temp := TreeNode{
		8, nil, nil,
	}
	temp2 := TreeNode{
		5, nil, nil,
	}
	//temp3 := TreeNode{
	//	5, nil, nil,
	//}
	//temp4 := TreeNode{
	//	5, nil, nil,
	//}
	root := TreeNode{
		1,
		&TreeNode{
			2,
			&TreeNode{
				4,
				&temp,
				nil,
			},
			&temp2,
		},
		&TreeNode{
			3,
			&TreeNode{
				6,
				nil,
				nil,
			},
			&TreeNode{
				7,
				nil,
				nil,
			},
		},
	}
	fmt.Println(lca(&root, &temp, &temp2).Val)
}
